Data compression is widely used in a variety of applications to reduce consumption of data storage space, transmission bandwidth, or both. Example applications of data compression include digital video, image, speech and audio coding. Digital video coding, for example, is used in wide range of devices, including digital televisions, digital direct broadcast systems, wireless communication devices, personal digital assistants (PDAs), laptop or desktop computers, digital cameras, digital recording devices, video gaming devices, cellular or satellite radio telephones, or the like. Digital video devices implement video compression techniques, such as MPEG-2, MPEG-4, or H.264/MPEG-4 Advanced Video Coding (AVC), to transmit and receive digital video more efficiently.
In general, video compression techniques perform spatial prediction, motion estimation and motion compensation to reduce or remove redundancy inherent in video data. In particular, intra-coding relies on spatial prediction to reduce or remove spatial redundancy in video within a given video frame. Inter-coding relies on temporal prediction to reduce or remove temporal redundancy in video within adjacent frames. For inter-coding, a video encoder performs motion estimation to track the movement of matching video blocks between two or more adjacent frames. Motion estimation generates motion vectors, which indicate the displacement of video blocks relative to corresponding video blocks in one or more reference frames. Motion compensation uses the motion vector to generate a prediction video block from a reference frame. After motion compensation, a residual video block is formed by subtracting the prediction video block from the original video block.
A video encoder applies transform, quantization and lossless source coding processes (i.e. entropy coding) to further reduce the bit rate of the residual block produced by the video coding process. Lossless coding techniques are used in the final stages of video encoders, and in various other coding applications, prior to storage or transmission of the encoded data. Lossless source coding generally involves the application of arithmetic codes or variable length codes (VLCs) to further compress residual coefficients produced by the transform and quantization operations. Examples of lossless coding techniques include context-adaptive binary arithmetic coding (CABAC) and context-adaptive variable length coding (CAVLC), which may be used as alternative lossless coding modes in some encoders. Other possible lossless coding techniques include variable-to-fixed length codes, sometimes referred to as VF codes. Examples of well-known VF codes include Tunstall codes and Khodak codes. A video decoder performs lossless decoding to decompress residual information for each of the blocks, and reconstructs the encoded video using motion information and the residual information.